package leetcode_ago.string_and_array;

/**
 * 数组右旋k个位置：
 * 给你一个数组，将数组中的元素向右轮转 k个位置，其中k是非负数。(k合法)
 * 1 <= nums.length <= 105
 * -2^31 <= nums[i] <= 2^31 - 1
 * 0 <= k <= 105
 * eg:输入: nums = [1,2,3,4,5,6,7], k = 3
 * 输出: [5,6,7,1,2,3,4]
 * 解释:
 * 向右轮转 1 步: [7,1,2,3,4,5,6]
 * 向右轮转 2 步: [6,7,1,2,3,4,5]
 * 向右轮转 3 步: [5,6,7,1,2,3,4]
 */
//public class Num189_RotateArray {
//    public  void rotate(int[] nums, int k) {
//        //暴力解题，一个一个挪，挪k次
//        for (int i = 0; i < k; i++) {
//            //获取数组末尾元素
//            int n=nums[nums.length-1];
//            for (int j=nums.length-2;j>=0;j--) {
//                nums[j+1]=nums[j];
//            }
//            nums[0]=n;
//        }
//    }
//}

/**
 * 三步翻转法
 * (右移k，左移nums.length-k)
 */
public class Num189_RotateArray {
    public  void rotate(int[] nums, int k) {
        k=k% nums.length;
        k= nums.length-k;
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
        reverse(nums,0,nums.length-1);
    }

    private  void reverse(int[] nums,int left, int right) {//反转
        while(left<right){
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            left++;
            right--;
        }
    }
}